The present invention is related to multi level dequeueing of traffic in switching networks when multiple sources and destinations are involved, with each source having traffic destined to different destinations over multiple prioritized queues. Any scheme that is fair in resource allocation can be used for selection of different prioritized queues. The multi level dequeueing is especially useful for high bandwidth network applications, which makes it feasible to implement scalable switches with current technology.
In high speed switching networks, the switch design involves collecting and queueing of incoming traffic (ex: packets or ATM cells) from many sources (ex: physical media). Each source could have traffic destined to different destinations over different priorities. Incoming traffic is queued based on per destination or per-destination and per priority queue. As the number of sources and destinations increase, and/or as each source and destination traffic bandwidth increases it could be impossible to build a switching module that can switch by queueing and dequeueing traffic at very high bandwidths. The technology limitations would make it impossible to build switches beyond certain bandwidth with single level of queueing and dequeueing.
The purpose of the present invention is to build network switches that can scale to any bandwidth by using multi node queueing and multi level dequeueing. Each queueing/dequeueing segment can run only at a fraction of the total bandwidth. The arbitrator collects information from all queues of the lower level dequeueing segments and by processing the information from different segments based on certain algorithm (ex; weighted round robin algorithm) it will give back dequeueing information to each segment. The arbitrator needs to get only enough information from all its lower level segments for current dequeueing interval. For each lower level segment the arbitrator can receive information from both the queueing logic and the destination of the traffic. The approach can be extended to any number of dequeueing levels by giving enough time to transfer the data from the buffer queues to the destinations.
The present invention pertains to a switch for switching traffic from N sources to M destinations, where M and N are each an integer greater than or equal to 2. The switch comprises K segments, where K is greater than or equal to 2 and is an integer. Each segment receiving traffic from R of the N sources, where 1xe2x89xa6R less than N and is an integer, and all K segments in total receiving traffic from the N sources. Each segment collecting and queuing traffic from the respective R sources. The switch comprises an arbitrator which receives information from the destinations regarding if they can receive data or not, and from the K segments about the traffic they have for different destinations.
The present invention pertains to a method for switching traffic from N sources to M destinations, where M and N are each an integer greater than or equal to 2. The method comprises the steps of receiving traffic from the N sources at input ports of K segments, where K is greater than or equal to 2 and is an integer. Each segment receiving traffic from R of the N sources where 1xe2x89xa6R less than N and is an integer. Then there is the step of sending traffic from any segment to a destination through an output port of an arbitrator which connects to each segment.
The present invention pertains to an arbitrator which receives information from M destinations regarding if they can receive data or not arising from N sources, and from K segments about the traffic they have for different destinations arising from the N sources. Each segment has input ports having a line rate L1, where K and M and N are each an integer greater than or equal to 2. The arbitrator comprises output ports each having a line rate L2, and a combination of an input port and output port together form a queue/dequeue node having a bandwidth of N/K*L1+M*L2. The arbitrator comprised an arbitrator controller that selects which destination is to receive traffic from a corresponding source and allows the traffic to flow through an output port to the destination.
The present invention pertains to a segment which receives traffic from R of N sources, where 1 is less than or equal to R which is less than N and is an integer, and N is an integer greater than or equal to 2. The segment comprises input ports, each having a line rate L1, which receive traffic from the respective R sources. The segment comprises queues associated with destinations which store traffic received at the input ports for the destination.